import java.util.Arrays;


public class MergeSoft {
	public static int[] mergeSort(int[] array){
		//If the array length it's = 0||1, it's sorted.
		if(! (array.length > 1))
			return array;
		//Makes two arrays, the left part and the right part of the original array
		int middle =  array.length/2;
		int [] left = new int[middle];
		int[] right = new int[array.length - middle];
		
		for(int i = 0; i<middle ; i++){
			left [i] = array[i];
		}
		for(int i = middle , j =0;i<array.length ; i++,j++){
			right[j]=array[i];
		}
			

		
		left = mergeSort(left);
		right = mergeSort(right);
		int[] result = new int [left.length + right.length];
		int k = 0;
		while(left.length != 0 && right.length != 0){
			if (left.length != 0 && left[0]<right[0]){
				result[k++] = left[0];
				left = Arrays.copyOfRange(left, 1, left.length);
			}else{
				result[k++]= right[0];
				right = Arrays.copyOfRange(right, 1, right.length);
			}
		}
		
		while(left.length != 0){
			result[k++] = left[0];
			left = Arrays.copyOfRange(left, 1, left.length);
		}
		while(right.length != 0){
			result[k++]= right[0];
			right = Arrays.copyOfRange(right, 1, right.length);
		}
		return result;
	}
	
	public static void main(String[] args) {
		int[] array = {45,7,34,9, 7,23,65,90,9,12,21,41,108,234,1,1,2};
		array = mergeSort(array);
		for(int a : array)
			System.out.print(a + "-");
	}
}
